#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;


LL k(LL a,LL b,LL mod)
{
	int sum=1;
	while(b){
		if(b&1) sum=a*sum%mod;
		a=a*a%mod;
		b>>=1;
	}
	return sum%mod;
}


int main()
{
	int n;
	cin>>n;
	
	for(int i=0;i<n;i++){
		LL a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		printf("%lld\n",k(a,b,c));
	}
	
	return 0;	
} 
